import numpy as np

class MEDWithDP():
    

    def __init__(self, source, target, costOfDelete = 1, costOfReplace = 1, costOfAdd = 1):
        self.source = "#" + source
        self.target = "#" + target
        self.source_len = len(self.source)
        self.target_len = len(self.target)
        self.costOfDelete = costOfDelete
        self.costOfReplace = costOfReplace
        self.costOfAdd = costOfAdd
        self.back_trace = [["undecided" for j in range(self.target_len)] for i in range(self.source_len)]
        self.dp = np.zeros((self.source_len, self.target_len))
        for i in range(self.source_len):
            self.dp[i,0] = i
        for i in range(self.target_len):
            self.dp[0,i] = i
        
    def fillDpMetrix(self, printEveryTime = False):
        for i in range(1, self.source_len):
            for j in range(1, self.target_len):
                self.dp[i, j] = self.dpMethod(i, j)
                if printEveryTime == True:
                    print(self.dp)
        print(self.dp)

    def dpMethod(self, i, j):
        DelCostRenew = self.dp[i-1, j] + self.costOfDelete
        AddCostRenew = self.dp[i, j-1] + self.costOfAdd
        RepCostRenew = self.dp[i-1, j-1] + self.costOfReplace
        if self.source[i] == self.target[j]:
            RepCostRenew = self.dp[i-1, j-1]
        minOfDp = min(DelCostRenew, AddCostRenew, RepCostRenew)
        return minOfDp

    def traceBack(self):
        for i in range(1, self.source_len):
            for j in range(1, self.target_len):
                bestDecision = "Keep     "
                bestCost = self.dp[i, j]
                if self.dp[i-1, j] < bestCost:
                    bestDecision = "Delete   "
                    bestCost = self.dp[i-1, j]
                if self.dp[i, j-1] < bestCost:
                    bestDecision = "Add      "
                    bestCost = self.dp[i, j-1]
                if self.dp[i-1, j-1] < bestCost:
                    bestDecision = "Replace  "
                    bestCost = self.dp[i-1, j-1]
                
                self.back_trace[i][j] = bestDecision
        self.back_trace[0][0] = "Begin    "
        for i in range(1, len(self.back_trace[0])):
            self.back_trace[0][i] = "Add      "
        for i in range(1, len(self.back_trace)):
            self.back_trace[i][0] = "Delete   "
        for i in range(len(self.back_trace)):
            print(self.back_trace[i])

    def run(self,printEveryTime = False):
        self.fillDpMetrix(printEveryTime)
        self.traceBack()

if __name__ == '__main__':
    sourceString = input("Please input SOURCE string.")
    targetString = input("Please input TARGET string.")
    costOfDelete = int(input("Please input COST OF DELETE."))
    costOfAdd = int(input("Please input COST OF ADD."))
    costOfReplace = int(input("Please input COST OF REPLACE."))
    printEveryTime = input("Whether or not print dp process? yes/no")
    printEveryTimeBool = False
    if printEveryTime == "yes":
        printEveryTimeBool = True
    MED = MEDWithDP(source = sourceString, target = targetString, costOfAdd = costOfAdd, costOfDelete = costOfDelete, costOfReplace = costOfReplace)
    MED.run(printEveryTimeBool)



